package 递归回溯;

import java.util.*;

public class No301删除无效的括号 {

    /**
     * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
     * 返回所有可能的结果。答案可以按 任意顺序 返回。
     * <p>
     * 示例 1:
     * 输入: "()())()"
     * 输出: ["()()()", "(())()"]
     * 示例 2:
     * 输入: "(a)())()"
     * 输出: ["(a)()()", "(a())()"]
     * 示例 3:
     * 输入: ")("
     * 输出: [""]
     * <p>
     * 提示：
     * 1 <= s.length <= 25
     * s 由小写英文字母以及括号 '(' 和 ')' 组成
     * s 中至多含 20 个括号
     */

    //推荐方法 迭代法 优势一:从长到短,可以第一时间得到结果  优势二:思路清晰
    public List<String> removeInvalidParentheses(String s) {

        Set<String> set = new HashSet<>();
        set.add(s);

        while (true) {

            Set<String> iteratorSet = new HashSet<>(set);
            Iterator<String> iterator = iteratorSet.iterator();
            while (iterator.hasNext()) {
                String next = iterator.next();
                boolean valid = this.isValid(next);
                if (!valid) {
                    iterator.remove();
                }
            }

            //出来的就是符合的
            if (iteratorSet.size() > 0) {
                return new ArrayList<>(iteratorSet);
            }

            Set<String> tempSet = set;
            set = iteratorSet;
            iteratorSet = tempSet;

            //没有一个符合的,往下一层去找
            for (String item : iteratorSet) {

                for (int i = 0; i < item.length(); i++) {

                    if (item.charAt(i) == '(' || item.charAt(i) == ')') {
                        //截取后放入
                        set.add(item.substring(0, i) + item.substring(i + 1));
                    }

                }

            }

            //放到最后没有东西可以放了
            if (set.size() == 0) {
                break;
            }

        }

        return new ArrayList<>(set);
    }

    //计数法判断括号是否合法,比较好的判断方法
    public boolean isValid(String s) {

        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            }
            if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }

        //开括号不能多
        return count == 0;
    }


    private String s;
    private List<String> result = new ArrayList<>();

    //非推荐方法,暴力法
    public List<String> removeInvalidParenthesesNormal(String s) {
        this.s = s;
        this.dfs(0, new StringBuilder());
        if (this.result.size() == 0) {
            this.result.add("");
            return this.result;
        }
        Set<String> set = new HashSet<>(this.result);
        this.result = new ArrayList<>();
        this.result.addAll(set);
        return this.result;
    }

    private void dfs(int index, StringBuilder path) {
        if (this.result.size() != 0 && this.result.get(0).length() > (this.s.length() - index + path.length())) {
            //剪枝
            return;
        }
        if (index == this.s.length()) {
            boolean valid = this.isValidNormal(path);
            if (valid) {
                if (this.result.size() == 0) {
                    this.result.add(path.toString());
                    return;
                }
                if (this.result.get(0).length() == path.length()) {
                    this.result.add(path.toString());
                    return;
                }
                if (this.result.get(0).length() < path.length()) {
                    this.result.clear();
                    this.result.add(path.toString());
                }
            }
            return;
        }
        path.append(this.s.charAt(index));
        this.dfs(index + 1, path);
        path.deleteCharAt(path.length() - 1);
        this.dfs(index + 1, path);
    }

    //判断括号是否有效,可以直接判断 '(' 和 ')' 的数量
    private boolean isValidNormal(StringBuilder sb) {
        if (sb.length() == 0) {
            return false;
        }
        if (sb.charAt(0) == ')') {
            //闭括号起头,一定false
            return false;
        }

        Stack<Character> stack = new Stack<>();
        int i = 0;
        for (; i < sb.length(); i++) {
            if (sb.charAt(i) == '(' || sb.charAt(i) == ')') {
                stack.add(sb.charAt(i));
                i++;
                break;
            }
        }

        while (i < sb.length()) {

            char c = sb.charAt(i++);

            if (c != '(' && c != ')') {
                continue;
            }

            if (c == '(') {
                stack.add(c);
            } else {
                //当前元素: )
                if (stack.isEmpty()) {
                    return false;
                }

                if (stack.peek() == '(') {
                    stack.pop();
                } else {
                    stack.add(c);
                }

            }

        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        No301删除无效的括号 n = new No301删除无效的括号();
//        List<String> result = n.removeInvalidParenthesesNormal("()())()");
//        System.out.println(JSON.toJSONString(result));
//        List<String> result = n.removeInvalidParentheses(")))(((");
//        System.out.println(JSON.toJSONString(result));
    }

}
